package Day01;

import java.util.*;

/**
 * -------------------------------------------------------------------------------------------
 * 题目：
 *      给你root1 和 root2这两棵二叉搜索树。请你返回一个列表，其中包含两棵树中的所有整数并按 升序 排序。.
 * -------------------------------------------------------------------------------------------
 * 示例：
 *      输入：root1 = [2,1,4], root2 = [1,0,3]
 *      输出：[0,1,1,2,3,4]
 * -------------------------------------------------------------------------------------------
 * 方法：
 *      中序遍历+合并链表
 * -------------------------------------------------------------------------------------------
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public static void main(String[] args) {

    }
    public static List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        dfs(list1,root1);
        dfs(list2,root2);
        List<Integer> list = new ArrayList<>();
        merge(list,list1,list2);
        return list;
    }
    public static void merge(List<Integer> list,List<Integer> list1,List<Integer> list2){
        int i=0,j=0;
        while(i<list1.size()&&j<list2.size()){
            if(list1.get(i)<=list2.get(j)){
                list.add(list1.get(i));
                i++;
            }
            else{
                list.add(list2.get(j));
                j++;
            }
        }
        if(i==list1.size()){
            for(;j<list2.size();j++){
                list.add(list2.get(j));
            }
        }
        else{
            for(;i<list1.size();i++){
                list.add(list1.get(i));
            }
        }
    }
    public static void dfs(List<Integer> list,TreeNode root){
        if(root==null){
            return;
        }
        if(root.left!=null){
            dfs(list,root.left);
        }
        list.add(root.val);
        if(root.right!=null){
            dfs(list,root.right);
        }
    }
}